package com.hunter;

import java.lang.reflect.Array;
import java.util.Arrays;

public class ErFenChaZhao {
    // 需要一个有序数组
    // 二分查找
    public static int erFenChaZhao(int[] nums, int target) {
        // 设置指针和初值
        int i = 0;
        int j = nums.length - 1;
        // 范围内有东西
        while (i <= j) {
            // 设置中间值
            int m = (i + j) / 2;
            // 当目标数target小于中间值m （在中间值左边）
            if (target < nums[m]) {
                // 往中间值左边找 （将最大值减小）
                j = m - 1;
            }
            // 当目标数target大于中间值m （在中间值右边）
            else if (nums[m] < target) {
                // 往中间值右边找 （将最小值增大）
                i = m + 1;
            }
            // 找到了
            else {
                return m;
            }
        }
        return -1;
    }

    /*
    问题1:为什么是 i<=j 意味着区间内有未比较的元素，而不是 i<j ?

    答：当 i=j 指向同的元素（指向同一个元素）也会参与比较
     */



    /*
    问题2: （i+j）/2 有没有问题？两个正整数相加变成负数？

    答：如果 i 和 j 都是 int 类型并且它们的和超过了 int 的最大值，
    就会发生整数溢出，可能导致错误的结果。

    补充：同一个二进制数
    10111_1111_1111_1111..._1110

    不把最高位视为符号位，代表 32212255470
    把最高位视为符号位，代表 -1073741826
     */

    /*
    问题3：为什么都写成小于符号，有什么好处？

    答：可读性高

     */

    // 二分查找（改动版）
    // 视屏：https://www.bilibili.com/video/BV1Lv4y1e7HL?p=7&spm_id_from=pageDriver&vd_source=195bb86ac961b029cb2c435e8dd102ba
    public static int erFenChaZhaoNew(int[] nums, int target) {
        // 设置指针和初值
        int i = 0;
        int j = nums.length; // （没有-1）
        // 范围内有东西
        while (i < j) { // （没有等号）
            // 设置中间值
            int m = (i + j) / 2;
            // 当目标数target小于中间值m （在中间值左边）
            if (target < nums[m]) {
                j = m; // j指向的值一定不是查找目标，j只是作为边界
            }
            // 当目标数target大于中间值m （在中间值右边）
            else if (nums[m] < target) {
                // 往中间值右边找 （将最小值增大）
                i = m + 1;
            }
            // 找到了
            else {
                return m;
            }
        }
        return -1;
    }

    /*
    改动版：
    1. j 的含义：
     作为边界，指向的一定不是查找目标。

    2. while循环条件 i 不再等于 j：
     会发生死循环

     */
    public static int erFenChaZhaoBanlance(int[] nums, int target) {
        int i = 0, j = nums.length;
        while (1 < j - i) { // 范围内有大于一个元素
            int m = (i + j) / 2;
            if (target < nums[m]) {
                j = m;
            } else {
                i = m;
            }
        }
        if (nums[i] == target) {
            return i;
        } else {
            return -1;
        }
    }
    /*
    1.左闭右开的区间，i指向的可能时目标，而j指向的不是目标

    2.不再循环哪找去，循环只是为了缩小边界
    等范围只剩下i时，退出循环，
    在循环外比较，nums[i]与target

    3.循环内的平均比较次数减少了
     */


    // java中实现二分查找
    public static int binarySearchJava(long[] nums, int fromIndex, int toIndex, long key) {
        int low = fromIndex;
        int high = toIndex - 1;
        while (low <= high) {
            int m = (low + high) / 2;
            long midval = nums[m];
            if (midval < key) {
                low = m + 1;
            } else if (key < midval) {
                high = m - 1;
            } else {
                return m;
            }
        }
        return -(low + 1);
    }
    /*
    问题：为什么最后没找到的返回结果需要加上一个 -1 ？
    答：因为当目标值在 0索引上时，不加 -1 就难以区分找到和没找到。
     */

    // LeftMost 找最靠左的
    // Params:
    //        a - 待查找的升序数组
    //        target - 待查找的目标值
    // Returns:
    //        找到则返回最靠左索引
    //        找不到返回 -1
    //        返回 >= target的最靠左索引
    public static int erFenChaZhaoLeftMost(int[] nums, int target) {
        // 设置指针和初值
        int i = 0;
        int j = nums.length - 1;
        int candidate = -1;
        // 范围内有东西
        while (i <= j) {
            // 设置中间值
            int m = (i + j) / 2;
            // 当目标数target小于中间值m （在中间值左边）
            if (target < nums[m]) {
                // 往中间值左边找 （将最大值减小）
                j = m - 1;
            }
            // 当目标数target大于中间值m （在中间值右边）
            else if (nums[m] < target) {
                // 往中间值右边找 （将最小值增大）
                i = m + 1;
            }else{ // 当目标值等于中间值
                // 记录候选位置
                candidate = m;
                j = m-1;
            }
        }
        return candidate;
    }

    // RightMost 找最靠右的
    // Params:
    //        a - 待查找的升序数组
    //        target - 待查找的目标值
    // Returns:
    //        找到则返回最靠右索引
    //        找不到返回 -1
    //        返回 <= target的最靠右索引
    public static int erFenChaZhaoRightMost(int[] nums, int target) {
        // 设置指针和初值
        int i = 0;
        int j = nums.length - 1;
        int candidate = -1;
        // 范围内有东西
        while (i <= j) {
            // 设置中间值
            int m = (i + j) / 2;
            // 当目标数target小于中间值m （在中间值左边）
            if (target < nums[m]) {
                // 往中间值左边找 （将最大值减小）
                j = m - 1;
            }
            // 当目标数target大于中间值m （在中间值右边）
            else if (nums[m] < target) {
                // 往中间值右边找 （将最小值增大）
                i = m + 1;
            }else{ // 当目标值等于中间值
                // 记录候选位置
                candidate = m;
                i = m+1;
            }
        }
        return candidate;
    }

}
